3.11. Finding prefix sums is a generalization of global sum. Rather than simply finding the sum of n values, x0 +x1 +...+xn-1, the prefix sums are the n partial sums x0, x0 +x1, x0 +x1 +x2, ... , x0 +x1 +..+xn-1. a. Devise a serial algorithm for computing the n prefix sums of an array with n elements. b. Parallelize your serial algorithm for a system with n processes, each of which is storing one of the x is. c. Suppose n D 2k for some positive integer k. Can you devise a serial algorithm and a parallelization of the serial algorithm so that the parallel algorithm requires only k communication phases? d. MPI provides a collective communication function, MPI Scan, that can be used to compute prefix sums:
It operates on arrays with count elements; both sendbuf p and recvbuf p should refer to blocks of count elements of type datatype. The op argument is the same as op for MPI Reduce. Write an MPI program that generates a random array of count elements on each MPI process, finds the prefix sums, and prints the results.